package code.notdo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * author : yeswater
 * date : 2023/12/5
 * 电话号码的字母组合
 * 回溯
 * 0928-
 */

public class T017 {
    public static void main(String[] args) {
        String digits = "23";
        System.out.println(letterCombinations(digits));
    }

    // 想不出来^^^^
    public static List<String> letterCombinations1(String digits) {
        HashMap<Character, String[]> map = new HashMap<>();
        map.put('2', new String[]{"a", "b", "c"});
        map.put('3', new String[]{"d", "e", "f"});
        map.put('4', new String[]{"g", "h", "i"});
        map.put('5', new String[]{"j", "k", "l"});
        map.put('6', new String[]{"m", "n", "o"});
        map.put('7', new String[]{"p", "q", "r", "s"});
        map.put('8', new String[]{"t", "u", "v"});
        map.put('9', new String[]{"w", "x", "y", "z"});
        char[] chars = digits.toCharArray();
        Arrays.sort(chars);
        List<String> res = new ArrayList<>();
        for (char aChar : chars) {
            String[] arr = map.get(aChar);
            for (String s : arr) {
                
            }
        }
        return res;
    }

    /**
     * 出处:https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solutions/13575/leetcode-17-letter-combinations-of-a-phone-number-/
     */
    private static String[] map = {
            " ",    //0
            " ",    //1
            "abc",  //2
            "def",  //3
            "ghi",  //4
            "jkl",  //5
            "mno",  //6
            "pqrs", //7
            "tuv",  //8
            "wxyz"  //9
    };
    
    private static ArrayList<String> res;
    
    public static List<String> letterCombinations(String digits) {
        res = new ArrayList<>();
        if (digits.equals(""))
            return res;
        find(digits, 0, "");
        return res;
    }
    
    // 递归拼接组合字母
    public static void find(String digits, int index, String s) { // digits.length() 有几组字符
        // 越界时添加字符串
        if (index == digits.length()) {
            res.add(s);
            return;
        }
        
        char c = digits.charAt(index);
        String str = map[c - '0'];
        for (int i = 0; i < str.length(); i++) { // 一组有几个字符
            find(digits, index+1, s + str.charAt(i)); // s + str.charAt(i) 每次循环拼接一个字符
        }

    }
}
